{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第九章　随机梯度下降算法\n",
    "\n",
    "\n",
    "作者：[王何宇](http://person.zju.edu.cn/wangheyu)\n",
    "\n",
    "[浙江大学数学科学学院](http://www.math.zju.edu.cn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们之前曾经讨论过，对于经典优化问题\n",
    "$$\n",
    "\\min f(x), x\\in \\Omega \\subset \\mathbb{R}^n\n",
    "$$\n",
    "主要利用 $f$ 的连续性，通过 $f$ 在当前值 $x_k \\in \\Omega$ 的局部信息，如\n",
    "$$\n",
    "f_k := f(x_k), \\nabla f_k := \\nabla f(x_k), \\nabla^2f_k := \\nabla^2 f(x_k) \n",
    "$$\n",
    "等等，构建迭代公式，例如牛顿公式：\n",
    "$$\n",
    "x_{k + 1} = x_k - \\alpha_k\\nabla^2 f_k^{-1} \\cdot \\nabla f_k,\n",
    "$$\n",
    "其中\n",
    "$$\n",
    "\\nabla f_k = \\left.\\left(\\frac{\\partial f}{\\partial x_1}, \\frac{\\partial f}{\\partial x_2}, \\cdots, \\frac{\\partial f}{\\partial x_n}\\right)^T\\right|_{x = x_k} \n",
    "$$\n",
    "是 $f$ 在 $x_k$ 点的梯度，而\n",
    "$$\n",
    "\\nabla^2 f_k = \\left.\\left[\\frac{\\partial^2 f}{\\partial x_i \\partial x_j}\\right]_{n \\times n}\\right|_{x = x_k}\n",
    "$$\n",
    "是 $f$ 在 $x_k$ 点的海森阵（Hessian Matrix）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 梯度下降\n",
    "\n",
    "这么做的理论依据是大家非常熟悉的 Taylor 展开，或者说 Taylor（中值）定理：令 $f: \\mathbb{R}^n \\to \\mathbb{R}$ 连续可谓，$p \\in \\mathbb{R}^n$，则存在 $t \\in (0, 1)$，使\n",
    "$$\n",
    "f(x + p) = f(x) + \\nabla f(x + tp)^Tp,\n",
    "$$\n",
    "特别地，对于 $f$ 二阶连续可微，存在 $t \\in (0, 1)$，使得\n",
    "$$\n",
    "f(x + p) = f(x)+ \\nabla f(x)^T p + \\frac{1}{2} p^T\\nabla^2 f(x + tp) p.\n",
    "$$\n",
    "在上式中令 $t = 0$，再求（这里假设 $\\nabla^2 f_k$ 总是正定的）\n",
    "$$\n",
    "\\Delta x_k = \\mathrm{argmin}_p f(x_k + p), x_{k + 1} = x_k + \\Delta x_k,\n",
    "$$\n",
    "就是牛顿迭代法（优化）。然而此方法对 $f$ 的连续性要求高，同时每一步迭代都要求解线性方程组：\n",
    "$$\n",
    "\\nabla^2 f_k \\Delta x_k = -\\nabla f_k,\n",
    "$$\n",
    "因此很多场合不适用或者代价过高。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因此一个替代办法就是回到第一个方程，同样令 $t = 0$，则有\n",
    "$$\n",
    "f_{k + 1} \\approx f_k + \\nabla f_k^T p,\n",
    "$$\n",
    "显然，当 $p = -\\nabla f_k^T$ 时，有\n",
    "$$\n",
    "\\nabla f_k^T p \\leq -\\nabla f_k^T \\nabla f_k = -\\|\\nabla f_k\\|_2^2,\n",
    "$$\n",
    "由此得到梯度下降公式：\n",
    "$$\n",
    "x_{k + 1} = x_k + \\alpha p_k = x_k - \\alpha \\nabla f_k.\n",
    "$$\n",
    "此处 $\\alpha > 0$ 是步长。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们看到，$-\\nabla f_k$ 是从 $x_k$ 出发下降最快的方向，因此对充分小的 $\\alpha$，我们总是能确保 $f_k$ 下降的。至于最优的 $\\alpha$ 是多少，则要根据实际问题具体分析。这里一般都会采取一个比较保守的策略，既确保目标函数值下降，同时又确保迭代算法稳定。因此只会采用一个下降的下界约束，甚至对复杂问题，定为一个小常数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最小二乘拟合\n",
    "\n",
    "为了便于展开讨论，我们从一个大家熟知的模型算法入手。已知二维数据 $(x_i, y_i)$，$i = 1, 2, \\cdots, m$，我们希望寻找：\n",
    "$$\n",
    "y = f(x) = \\sum_{j = 1}^n w_j \\phi_j(x),\n",
    "$$\n",
    "其中 $w_j \\in \\mathbb{R}$ 是待定系数，$\\phi_j(x) : \\mathbb{R}^2 \\to \\mathbb{R}$ 是一组基底函数，$j = 1, 2, \\cdots, n$，通常由经验决定。这里一般有 $m >> n$。（比如过一堆二维散乱点求最优直线。）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从线性方程组角度看，上述问题显然是超定的，不存在解。但我们可以转而求优化问题：\n",
    "$$\n",
    "\\min_{w} R = \\frac{1}{2}\\sum_{i = 1}^m\\left[\\sum_{j = 1}^n w_j \\phi_j(x_i) - y_i\\right]^2,\n",
    "$$\n",
    "其中 $w = (w_1, w_2, \\cdots, w_n)^T \\in \\mathbb{R}^n$。这就是我们熟悉的线性最小二乘拟合。在更一般的拟合问题中，$w$ 可以是非线性参数，而优化空间的范数也可以有更广泛的选择。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们下面以线性最小二乘拟合为例，介绍一种概率优化算法。首先，对线性最小二乘拟合，最简单的做法是采用梯度下降法：\n",
    "$$\n",
    "\\begin{array}{l}\n",
    "\\nabla R_k = \\displaystyle\\left(\\frac{\\partial R}{\\partial w_j}\\right)^T = \\displaystyle\\left.\\left(\\sum_{i = 1}^m\\left[\\sum_{j = 1}^n w_j\\phi_j(x_i) - y_i\\right] \\cdot \\phi_j(x_i)\\right)^T\\right|_{w = w_k}\\\\\n",
    "w_{k + 1} = w_k + \\alpha \\nabla R_k.\n",
    "\\end{array}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个经典的多维梯度下降算法，在机器学习等领域，被称为批量梯度下降法（Batch Gradient Descent, BGD）。它的实际效果其实不错，但问题是它的每一步迭代，都会用到全部数据集 $(x_i, y_i), i = 1, 2, \\cdots, m$。这个在经典的科学实验拟合中不是什么问题，最多丢弃一些看上去明显不对的“野点”（洗数据...）。但是当前机器学习和数据分析领域的典型特点是：\n",
    "1. 数据量极大，$m$ 可能是百万级，甚至更大；\n",
    "2. $x_i$ 是高维数据，维数可能是上万维甚至更高；\n",
    "3. $y_i$ 不准确，混杂了大量噪音，只有概率期望意义上的正确性。\n",
    "\n",
    "在这种形势下， BGD 不但计算量极大，而且吸收了全部噪音数据，得到的结果很可能反而不理想。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**例：混杂了噪音的测试算例。**\n",
    "构建\n",
    "$$\n",
    "y_i = x_i^2 + \\varepsilon,\n",
    "$$\n",
    "其中 $\\varepsilon \\sim N(0, 0.1)$ 代表噪音数据，$x_i \\sim U(0, 10)$ 代表输入。我们用于回归的模型为：\n",
    "$$\n",
    "f(x) = w_1 + w_2 x + w_3 x^2.\n",
    "$$\n",
    "当然还可以写的更高大上一点：\n",
    "$$\n",
    "f(x) = \\sum_{j = 1}^n w_j \\phi_j(x) + b, \n",
    "$$\n",
    "其中 $n = 1, 2$, $\\phi_1(x) = x$, $\\phi_2(x) = x^2$，也就是说其实这里的 $(b, w_1, w_2)$ 对应之前的 $(w_1, w_2, w_3)$。通常，称 $b$ 为置偏（bias）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
